The storage and transmission of high volumes of digitized road-map or other topology data poses several challenges in designing embedded product and network architectures for mobile and distributed computing.
First, the high volumes of data needed may limit the size of the mapped geographic area to be stored and distributed on data storage media. This is an important factor, considering the high cost of large semiconductor memory and the mechanical limitations of using devices with rotating media in a mobile environment.
Second, downloading digitized road-map data from a remote central site to a mobile device poses another limitation because of the high transmission cost through conventional communications channels such as a cellular telephone network.
Data compression can alleviate these limitations. It can minimize storage and retrieval delay of desired road-map data. Uncompressed road-map data may be stored in mass-storage media such as hard disk, compact disk, or tape. When a certain block of such data is downloaded for processing by an embedded system, the central processing unit (CPU) on the embedded system is likely to be idle during much of the search and transfer time required. If the road-map data on the storage medium were to be compressed by a certain factor, the block of such data would be commensurably smaller in size, and the search for and transfer time of these data to the embedded system would be reduced. During the shorter duration time of the block of compressed road data, the otherwise idle CPU can be used to carry out the decompression of the data, provided the CPU is of sufficient computational capacity. Thus, otherwise idle, disk-bound CPU cycles can be traded for reduced storage, search, and data transfer times and costs, resulting in a natural balance between data handling and computation. Data compression can result in savings in semiconductor memory and in transmission bandwidth. These savings can offset the possible extra cost of CPU-cycles for decompression. In the prior art, a road line is typically approximated by a sequence of linear road segments. These road segments are usually represented by data structures that include at least two pairs of position coordinate values, one pair for each end of the road segment. Optimization in memory usage is achieved by:
minimizing the length of the fields used for storing the binary coordinate values. This sacrifices some precision, which is tolerable as long as the fields do not impact proper and correct operation of the applications accessing the digitized road-map data; PA1 defining the position coordinates relative to some local reference position. This reference position is usually associated with a selected geographical area. It is well known that road map coordinates relative to a reference position can be encoded in shorter data fields without sacrificing any precision. Such representations of road-map coordinate data have been reported by commercial map database vendors, including Navtech and Etak.
There exist other road-map data compression devices and methods, which exploit repetitive bit patterns in unstructured binary data, build a dictionary of representative repetitive patterns, and then replace each instance of an observed repetitive pattern with the corresponding index of its closest representative in the dictionary. This approach is commonly referred to as the Lempel-Ziv compression. Such methods make no use of known characteristics about the structure of the road-map data, such as map topology and road attributes; consequently, their effectiveness is limited. Compression ratios attained by such methods typically range from 2 to 3, and sometimes they are even lower. Another disadvantage of the Lempel-Ziv method is that the compressed data it produces cannot always be accessed directly by a particular application, because the orthogonal substitution of binary patterns may prevent the application from recognizing meaningful structures. For example, the Lempel-Ziv compression may replace a binary pattern, the first part of which is a portion of a coordinate value and the second part of which is a partial road attribute value. If the whole pattern is replaced with a single index value, neither the coordinate value nor the road attribute value can be recognized without running the appropriate decompression algorithm.
In general, compressed data has to be decompressed in its entirety before an application can search for the desired portion of the map data. This requirement may increase the computational cost of decompression, as well as the decompression buffer size. Otherwise, an alternative approach could be used to perform a meaningful partitioning of the map data into parcels and then, to perform a Lempel-Ziv compression on each parcel separately. It could be very difficult to anticipate an optimal partitioning of the map data because each application may access the data in a different and unpredictable manner. Examples of such applications are map-matching algorithms that track the movement of a vehicle along road network, route-planning algorithms or map display programs. The partitioning could also further limit the compression ratio.
With Huffmann encoding, data values are stored in data fields of varying lengths, thus realizing a savings in total storage. Frequent and redundant data values are encoded in shorter fields, while rarely used data values require longer fields. No prior art work made significant use of Huffmann encoding for road-map data compression.
In the prior art, attempts have been made to utilize the knowledge of the road line shapes for compression purposes. Kasser, in German patent DE 68907403 assigned to Bosch GmbH, replaced the linear approximation of route segments by curved segments defined by approximate radii of curvature. However, many non-linear road segments have complex shapes which could be much more efficiently encoded if the fixed radius curvature was not the only repeatedly used type of shape for compression. So, the practicality of Kasser approach is limited.
In European Patent Application Publication number 0 219 930, White and Loughmiller of Etak, Inc. disclosed another solution whereby the mapped area is split into pieces called "carriers" along natural boundary lines, in order to minimize the number of cases when a road line had to span several, separately represented map areas. They defined a model for a hierarchical nesting of these mapped areas which, unfortunately, can be conveniently and efficiently applied only for specific and limited topologies.
In U.S. Pat. No. 4,729,127, Chan used techniques for compressed representation of cultural terrain features such as rivers, lakes, and natural rock-formations as well as man-made cultural features such as roads, towns, and significant structures on three-dimensional map surfaces in order to aid aircraft and other vehicle navigation. Chan uses differential encoding to identify subsequent points on a line. This technique, however, is not effective for compressing complex networks of intersecting road lines of a variety of shapes.
Another technique involving interpolation of three-dimensional surfaces was published by Cozart, in the report AFOSR-TR-83-1333 of the Department of Mathematics & Computer Science, The Citadel, Mathematical & Information Sciences Directorate, Air Force Office of Scientific Research. Cozart derived bicubic polynomials to represent the terrain surface over small subgrids. He defined a rectangular grid with a constant grid spacing that yielded a number of data points on the vertical and horizontal boundary of a square subgrid. The elevation data on the boundary line was then interpolated to extend it smoothly into the subgrid.
In U.S. Pat. No. 5,216,726, Heaton used a token to signify that the coordinates of similar polygons are all separated by a given distance. He also used a data compression technique based on the observation that circuits were comprised of arrays of similar polygonal shapes having the same orientation. Furthermore, he eliminated the redundancy in representing the coordinates of the vertices of square shapes by replacing a repeated coordinate value for two adjacent vertices with a single value and a special token. Heaton reduced the data field length for representing the coordinate position of a vertex of a polygon by replacing the distance between the vertex and a common reference point with a relative distance value between the vertices of two adjacent polygons. Furthermore, common adjacent distances or delta values were also represented by special tokens. Heaton's invention is restricted to very specific and limited types of shapes and repetitions. It has more significance in the domain of integrated circuit design with a higher degree of regularity in its topology than the domain of road maps or similar structures.
The above methods do not contribute significantly to the compression efficiency of road-map data. A more effective approach employing a combination of efficient compression and decompression techniques would be of great value to the envisioned objectives of digitized road map processing. More efficiently eliminating much of the inherent redundancy in the topology and attributes that characterize road-map data would provide better compression than is now available. Effectively decompressing the compressed road-map data and reconstructing a faithful reproduction of the original road-map data, would significantly contribute to the design and deployment of more effective and economically affordable embedded road-map data processing subsystem architectures.